其他
质数判定的几种方法及性能优化
素性测试 (Primality test)
什么是质数?
遍历取模
遍历取模函数式版本
正则表达式法
开方优化
埃拉托斯特尼筛法:用质数找出质数
性能比较
素性测试 (Primality test)
什么是质数?
质数(Prime number,又称素数),指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。
遍历取模
判断当前整数是否为质数最常规的方法,就是让它与所有小于它的数(且大于1)取模。
const isPrime = num => {
for (let i = 2; i < num; i++)
if (num % i === 0) return false;
return num > 1;
}
const log = n =>{
console.time(n);
console.log(n, isPrime(n));
console.timeEnd(n);
}
[2,3,4,5,6,7,8,9,10,11,197,977,7919,51977,99991,999983,999987,1000000007,12345678911].map(log);
...
10 false
10: 0.025ms
11 true
11: 0.025ms
197 true
197: 0.034ms
977 true
977: 0.063ms
7919 true
7919: 0.362ms
51977 true
51977: 2.624ms
99991 true
99991: 1.359ms
999983 true
999983: 5.989ms
999987 false
999987: 0.024ms
1000000007 true
1000000007: 6007.705ms
12345678911 false
12345678911: 0.046ms
遍历取模函数式版本
可以用数组方法替代for循环。
正则表达式法
1
的个数来实现监测质数的功能的。此正则表达式分成 由”|”分割两部分: /^1?$/
和/^(11+?)\1+$/
。(11+?)
表示至少有两个1,(11+?)\1
中的\1
表示对前面的匹配的引用。\1+
表示前面的(11+?)
出现至少一次,相当于(11+?){2,}
。整个式子的含义为至少出现两次(11+?)。也就是说,所匹配的数可以写成两个大于2的整数的乘积。而?
通过backtrace穷举所有的可能行,从而完成匹配所有的合数。|
连接,不匹配的就只能是质数了。开方优化
以上方案中,遍历取模是适用而比较广的,它能检测到质数相对较大。
质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。除了1以外,两个没有其他共同质因子的正整数称为互质。
1没有质因子。 5只有1个质因子,5本身。(5是质数) 6的质因子是2和3。(6 = 2 × 3) 2、4、8、16等只有1个质因子:2。(2是质数,4 =2²,8 = 2³,如此类推) 10有2个质因子:2和5。(10 = 2 × 5)
筛法:用质数查找质数
开方优化方法将循环次数从n减少到Math.sqrt(n),性能大幅度提升。
那么能否进一步减少循环次数?答案是肯定的。
遍历取模是对质数才有效,在有限的整数序列中,质数远少于合数。如果只对质数集合遍历,将大大循环次数。
所以,关键在于找出小于Math.sqrt(n)的质数集合。
此时需用筛法:筛法(挨拉托色尼筛法)是一种用来求所有小于N的素数的方法。把从2(素数是指大于1的自然数)开始的某一范围内的正整数从小到大按顺序排列,逐步筛掉非素数留下素数。
筛法求素数的基本思想是:把从2到N的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍数,直到根号N的倍数为止,剩余的即为2~N之间的所有素数。
所以,100以内的素数都可以通过2,3,5,7筛选出来:
代码实现即为:
我们需要一个[2,3,5,7… Math.sqrt(n)]集合,可以通过生成器实现:
genPrimes将生成一个质数有序集合,判定质数只需对该集合遍历取模就行。
性能比较
开方优化>>遍历取模>函数式遍历取模>正则表达式。
参考资料
A wild way to check if a number is prime using a regular expression | by Mark Sauer-Utley | ITNEXT 正则表达式检测质数 | HE Tao Demystifying The Regular Expression That Checks If A Number Is Prime – The Codeumentary
往期推荐